package com.fengye.algorithms.leecode;

/**
 * @Author fengye
 * @Date 2023/4/24 11:23
 **/
public class SubarrayProductLessThanK713 {

    public static void main(String[] args) {
        new SubarrayProductLessThanK713().numSubarrayProductLessThanK1(new int[]{10,5,2,6}, 100);
    }

    public int numSubarrayProductLessThanK1(int[] nums, int k) {
        int n = nums.length, ret = 0;
        int prod = 1, i = 0;
        for (int j = 0; j < n; j++) {
            prod *= nums[j];
            while (i <= j && prod >= k) {
                prod /= nums[i];
                i++;
            }
            ret += j - i + 1;
        }
        return ret;
    }

    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if(nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        int start = 0, end = 0;
        int n = 0;
        int J = 1;
        while (end < len) {
            J *= nums[end];
            // 如果积比k大，则滑动窗口
            while (J >= k && start <= end) {
                J /= nums[start];
                start++;
            }
            // 这里是关键，小于k，在这个区间内的个数是end-start+1
            n += end - start + 1;
            end++;
        }

        return n;
    }
}
